#include "stdio.h"
#include "stdlib.h"

#define LIST_INIT_SIZE 100  //初始分配量
#define LISTINCREMENT 10  //分配增量

typedef int ElemType;

//数据对象
typedef struct {
	ElemType* elem;
	int length;
	int listsize;
}SqList;

//初始化线性表
bool InitList_Sq(SqList &L) {
	L.elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));
	if (!L.elem) return false;
	L.length = 0;
	L.listsize = LIST_INIT_SIZE;
	return true;
}

//线性表插入元素
bool ListInsert_Sq(SqList& L, int i, ElemType num) {
	if (i<1 || i>L.length+1) return false;
	if (L.length >= L.listsize) {
		ElemType* newspace = (ElemType*)realloc(L.elem, (L.listsize + LIST_INIT_SIZE) * sizeof(ElemType));
		if (!newspace) return false;
		L.elem = newspace;
		L.listsize += LIST_INIT_SIZE;
	}
	ElemType* p = &L.elem[i - 1];
	for (ElemType* q = &L.elem[L.length - 1]; q >= p; q--) {
		*(q + 1) = *q;
	}
	*p = num;
	L.length++;
	return true;
}

//线性表删除元素
bool ListDelete_Sq(SqList &L, int i) {
	if (i<1 || i>L.length + 1) return false;
	ElemType* p = &L.elem[i-1];
	p = &L.elem[i];
	for (ElemType* q = &L.elem[L.length - 1]; p <= q; p++) {
		*(p - 1) = *p;
	}
	L.length--;
	return true;
}

//查找元素
int LocateElem_Sq(SqList L, ElemType num) {
	for (int i = 0; i < L.length; i++) {
		if (L.elem[i] == num) return ++i;
	}
	return 0;
}

//归并线性表
void MergeList_Sq(SqList LA, SqList LB, SqList& LC) {
	LC.length = LC.listsize = LA.length + LB.length;  //LC的长度为LA和LB的和
	LC.elem = (ElemType*)malloc(LC.listsize * sizeof(ElemType));  //为LC分配空间
	ElemType* pa = LA.elem;
	ElemType* pb = LB.elem;
	ElemType* pc = LC.elem;
	ElemType* pa_last = &LA.elem[LA.length - 1];
	ElemType* pb_last = &LB.elem[LB.length - 1];
	while (pa <= pa_last && pb <= pb_last) {  //遍历LA和LB
		if (*pa <= *pb) *pc++ = *pa++;  //判断pa和pb指向元素的大小，赋值过后指针向后移动
		else *pc++ = *pb++;
	}
	while (pa <= pa_last) *pc++ = *pa++;  //将剩下的元素赋值给LC
	while (pb <= pb_last) *pc++ = *pb++;
}

//线性表求并集
void union_Sq(SqList LA, SqList LB, SqList& LC) {
	for (int i = 0; i <= LA.length;i++) {  //遍历LA
		if(LocateElem_Sq(LB, LA.elem[i])) ListDelete_Sq(LA,i+1);  //如果该元素在LB中存在，则删除LA中的该元素
	}
	MergeList_Sq(LA, LB, LC);
}

//输出线性表
void Print_Sq(SqList L) {
	for (int i = 0; i < L.length; i++) {
		printf("%3d", L.elem[i]);
	}
	printf("\n");
}

int main() {
	ElemType e;
	SqList LA;
	InitList_Sq(LA);
	ListInsert_Sq(LA, 1, 3);
	ListInsert_Sq(LA, 2, 5);
	ListInsert_Sq(LA, 3, 8);
	ListInsert_Sq(LA, 4, 11);
	Print_Sq(LA);
	SqList LB;
	InitList_Sq(LB);
	ListInsert_Sq(LB, 1, 2);
	ListInsert_Sq(LB, 2, 6);
	ListInsert_Sq(LB, 3, 8);
	ListInsert_Sq(LB, 4, 9);
	ListInsert_Sq(LB, 5, 11);
	ListInsert_Sq(LB, 6, 15);
	ListInsert_Sq(LB, 7, 20);
	Print_Sq(LB);
	SqList LC;
	InitList_Sq(LC);
	MergeList_Sq(LA, LB, LC);
	Print_Sq(LC);
	union_Sq(LA, LB, LC);
	Print_Sq(LC);
	return 0;
}